/*
 * @Author: zxc
 * @Date: 2020-08-14 21:05:18
 * @LastEditTime: 2020-08-15 10:18:31
 * @LastEditors: zxc
 * @Description: 深度优先搜索
 */
const Colors = {
  WHITE: 0,
  GREY: 1,
  BLACK: 2,
};

// 初始化每个顶点的颜色
const initializeColor = (vertices) => {
  const color = {};
  for (let i = 0; i < vertices.length; i++) {
    color[vertices[i]] = Colors.WHITE;
  }
  return color;
};

/**
 * @Author: zxc
 * @Date: 2020-08-14 21:23:55
 * @func:深度优先遍历，我觉得书上讲的不行
 * 首先，我们之前的广度优先遍历用的是队列的数据结构，而深度优先则是用到的递归（递归在浏览器的实现其是栈）
 * 1. 我们depthFirstSearch接收两个参数，一个是图，一个是回调函数
 * 2. 我们获取到图的节点数组以及图的边的字典
 * 3. 我们初始化了每个节点的颜色 
 * 4. 我们将遍历图中的每个节点，如果当前节点所在的颜色字典中对应的key的色值为white，则对该结点进行深度遍历
 * 5. 这里我们调用了depthFirstSearchVisit方法，它接收四个参数，分别是：
 *      1. 当前节点
 *      2. 颜色字典
 *      3. 边字典
 *      4. 回调函数
 */
export const depthFirstSearch = (graph, callback) => {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = initializeColor(vertices);

  for (let i = 0; i < vertices.length; i++) {
    if (color[vertices[i]] === Colors.WHITE) {
      depthFirstSearchVisit(vertices[i], color, adjList, callback);
    }
  }
};

/**
 * 
 * 6. depthFirstSearchVisit中，首先，将接收到的这个节点在color中对应的key的色值置黑
 * 7. 如果有回调函数的话执行它
 * 8. 从边字典中获取当前传来的节点的对应节点
 * 9. 遍历这些节点
 * 10.如果这个节点的对对应的color中的value是white，则递归一下，再遍历这个结点
 * 11. 循环递归遍历结束，将当前遍历的这个结点在color中置黑，表示已经用过它了
 */
const depthFirstSearchVisit = (u, color, adjList, callback) => {
  color[u] = Colors.GREY;
  if (callback) {
    callback(u);
  }
  // console.log('Discovered ' + u);
  const neighbors = adjList.get(u);
  for (let i = 0; i < neighbors.length; i++) {
    const w = neighbors[i];
    if (color[w] === Colors.WHITE) {
      depthFirstSearchVisit(w, color, adjList, callback);
    }
  }
  color[u] = Colors.BLACK;
  // console.log('explored ' + u);
};


export const DFS = graph => {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = initializeColor(vertices);
  const d = {};//发现时间的字典
  const f = {}; //探索结束时间的字典
  const p = {}; //前溯节点的字典
  const time = { count: 0 };
  for (let i = 0; i < vertices.length; i++) {
    f[vertices[i]] = 0;
    d[vertices[i]] = 0;
    p[vertices[i]] = null;
  }
  for (let i = 0; i < vertices.length; i++) {
    if (color[vertices[i]] === Colors.WHITE) {
      DFSVisit(vertices[i], color, d, f, p, time, adjList);
    }
  }
  return {
    discovery: d,
    finished: f,
    predecessors: p
  };
};


const DFSVisit = (u, color, d, f, p, time, adjList) => {
  // console.log('discovered ' + u);
  color[u] = Colors.GREY;
  d[u] = ++time.count;
  const neighbors = adjList.get(u);
  for (let i = 0; i < neighbors.length; i++) {
    const w = neighbors[i];
    if (color[w] === Colors.WHITE) {
      p[w] = u;
      DFSVisit(w, color, d, f, p, time, adjList);
    }
  }
  color[u] = Colors.BLACK;
  f[u] = ++time.count;
  // console.log('explored ' + u);
};

